package leetcode.tree_problem;

/**
 * 236. 二叉树的最近公共祖先
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 */
public class 二叉树的最近公共祖先 {
    public TreeNode cur ;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        findAncestors(root , p , q);
        return cur;

    }
    public boolean findAncestors(TreeNode root , TreeNode p , TreeNode q){
        if (root == null){
            return false;
        }
        int left = findAncestors(root.left , p , q) ? 1 : 0;
        int right = findAncestors(root.right , p , q) ? 1 : 0;
        int mid = (p == root || q == root) ? 1 : 0;


        if (left + mid + right == 2){
            cur = root;
        }
        return (left + mid + right > 0) ? true : false;
        //挺没想到的居然能通过就这么顺下来了
    }
}
